 // 17题： https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
 
#include<unordered_map>
#include<vector>
#include<iostream>

using namespace std;
class Solution {
public:
    vector<string> ret;
    unordered_map<char, string> map = {
            {'2', "abc"},
            {'3', "def"},
            {'4', "ghi"},
            {'5', "jkl"},
            {'6', "mno"},
            {'7', "pqrs"},
            {'8', "tuv"},
            {'9', "wxyz"}
        };

    vector<string> letterCombinations(string digits) {
        if(digits.size() == 0) return ret;

        // unordered_map<char, string> map = {
        //     {'2', "abc"},
        //     {'3', "def"}
        // };

        // 以下代码会产生 segmentation fault: 为什么？map 不是这么构造的，下边这是Java 的写法
        // map['2'] = "abc";
        // map['3'] = "def";
        // map['4'] = "ghi";
        // map['5'] = "jkl";
        // map['6'] = "mno";
        // map['7'] = "pqrs";
        // map['8'] = "tuv";
        // map['9'] = "wxyz";

        
        backtrack("", digits, 0);
        return ret;
    }

    // track 保存组合，包括中间结果、最终结果
    // digits: 输入的数字，例如"23"
    // index: 输入数字的索引，如0: '2', 1:'3'
    // 基本符合回溯算法的框架，只通过参数中的index 遍历了digits 中的每个数字
    void backtrack(string track, string digits, int index){
        if(index == digits.size()){
            ret.push_back(track);
            return;
        }

        string str = map[digits[index]];
        for(int i = 0; i < str.size(); i++){
            track.insert(track.end(), str[i]);
            backtrack(track, digits, index + 1);
            track.erase(track.end()-1);
        }
        
    }
};

void print(vector<string> v){
    for(string s : v){
        cout<<s<<",";
    }
    cout<<endl;
}

void test_01(){
    Solution slu;
    vector<string> ret = slu.letterCombinations("23");
    assert(ret.size() == 9);
    print(ret);
}

void test_02(){
    Solution slu;
    vector<string> ret = slu.letterCombinations("234");
    assert(ret.size() == 27);
    print(ret);
}

void test_03(){
    Solution slu;
    vector<string> ret = slu.letterCombinations("2345");
    assert(ret.size() == 81);
    print(ret);
}

void test_04(){
    Solution slu;
    vector<string> ret = slu.letterCombinations("23457");
    assert(ret.size() == 324);
    print(ret);
}

int main(){
    // test_01();
    test_02();
    test_03();
    test_04();

    return 0;
}